无人机巡检航线规划[200分]

题目内容

某电力公司使用无人机对 $n$ 个电力塔进行巡检。每个电力塔 $i$ 位于坐标 $(x_i, y_i)$，无人机从基地（坐标 $(0,0)$）出发，需要依次飞达每个电力塔完成巡检后结束任务，无需返回基地。

无人机同一时刻只能飞向一个电力塔，请规划巡检顺序，使无人机飞行的总距离最短（两个坐标点间按曼哈顿距离计算，即 $|x_1-x_2| + |y_1-y_2|$），输出最短总距离。

输入描述

• $n$：电力塔数量，$1 \le n \le 15$
• $x_i, y_i$：第 $i$ 个电力塔的坐标，$0 \le x_i, y_i \le 200$

输出描述

输出最短总距离（整数）。

样例

样例 1

输入

3
1 2
3 1
2 3

输出

8

说明： 3 个电力塔：$A(1,2)$、$B(3,1)$、$C(2,3)$。基地为 $O(0,0)$。

• 巡检顺序 $A \to C \to B$：$O \to A$ 距离 $|1-0|+|2-0|=3$，$A \to C$ 距离 $|1-2|+|2-3|=2$，$C \to B$ 距离 $|2-3|+|3-1|=3$。总距离 $3+2+3=8$
• 巡检顺序 $A \to B \to C$：$O \to A$ 距离 3，$A \to B$ 距离 $|1-3|+|2-1|=3$，$B \to C$ 距离 $|3-2|+|1-3|=3$。总距离 9
• 巡检顺序 $B \to A \to C$：$O \to B$ 距离 4，$B \to A$ 距离 3，$A \to C$ 距离 2。总距离 9

其余顺序总距离均不小于 8，最短总距离为 8。

样例 2

输入

2
1 1
2 2

输出

4

说明： 2 个电力塔：$A(1,1)$、$B(2,2)$。基地为 $O(0,0)$。

• 巡检顺序 $A \to B$：$O \to A$ 距离 $|0-1|+|0-1|=2$，$A \to B$ 距离 $|1-2|+|1-2|=2$。总距离 $2+2=4$
• 巡检顺序 $B \to A$：$O \to B$ 距离 $|0-2|+|0-2|=4$，$B \to A$ 距离 $|2-1|+|2-1|=2$。总距离 $4+2=6$

最短总距离为 4。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let inputs = [];
rl.on('line', (input) => {
    inputs.push(input.split(' ').map(Number));
})
rl.on('close', () => {
    const n = inputs.shift()[0];
    const arr = inputs;
    
    // ========== 优化1：预计算距离矩阵 ==========
    // d[i][j] 表示塔 i 到塔 j 的曼哈顿距离
    const d = Array.from({length: n}, () => Array(n).fill(0));
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < n; j++) {
            d[i][j] = Math.abs(arr[i][0] - arr[j][0]) + Math.abs(arr[i][1] - arr[j][1]);
        }
    }
    
    const used = new Array(n).fill(false);  // 标记哪些塔已访问
    let count = 0;                          // 已访问数量，替代 filter
    const memo = new Map();                 // 记忆化缓存
    
    // ========== 优化2：dfs 返回"剩余距离" ==========
    // dfs(c) 表示：当前站在塔 c，飞完所有还没访问的塔，最少还要飞多远
    const dfs = (c) => {
        // 全部飞完了，剩余距离为 0
        if(count === n) return 0;
        
        // 用"当前位置 + 当前访问状态"作为缓存 key
        // 例如："2,true,false,true" 表示在2号塔，0号和2号已访问
        const key = c + ',' + used.join(',');
        if(memo.has(key)) return memo.get(key);
        
        let minExtra = Infinity;
        
        for(let i = 0; i < n; i++) {
            if(!used[i]) {
                used[i] = true;   // 去 i 号塔
                count++;          // 访问数 +1
                
                // 从 c 飞到 i 的距离 + 从 i 继续飞完剩下的距离
                const dist = d[c][i] + dfs(i);
                if(dist < minExtra) minExtra = dist;
                
                count--;          // 回溯：恢复访问数
                used[i] = false;  // 回溯：恢复状态
            }
        }
        
        memo.set(key, minExtra);
        return minExtra;
    }
    
    let ans = Infinity;
    for(let i = 0; i < n; i++) {
        used[i] = true;
        count = 1;
        
        // 总距离 = 基地(0,0)到 i 的距离 + 从 i 飞完剩余的距离
        const total = (arr[i][0] + arr[i][1]) + dfs(i);
        if(total < ans) ans = total;
        
        used[i] = false;
        count = 0;
    }
    
    console.log(ans);
})